package Sort;

public class HeapSort {
    /**
     * 堆排序 - heapSort
     * <p>
     * 时间复杂度:O(N * logN)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */

    private static void shiftDown(int[] array, int parent, int len) {
//        int child = 2 * parent + 1;
        int child = (parent << 1) + 1;//一定要加括号，+优先级高于<<
        while (child < len) {
            if (child + 1 < len && array[child] < array[child + 1]) {
                child++;
            }
            if (array[child] > array[parent]) {
                int tmp = array[child];
                array[child] = array[parent];
                array[parent] = tmp;

                parent = child;
                child = (parent << 1) + 1;
            } else {
                break;
            }
        }
    }

    private static void creatHeap(int[] array) {
        // 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆
        for (int i = (array.length - 1 - 1) >> 1; i >= 0; i--) {
            shiftDown(array, i, array.length);
        }
    }


    public static void heapSort(int[] array) {
        creatHeap(array);
        int end = array.length - 1;
        while (end > 0) {
            int tmp = array[end];
            array[end] = array[0];
            array[0] = tmp;
            shiftDown(array, 0, end);
            end--;
        }
    }
}
